package leetcode.hot100;

import com.sun.org.apache.xalan.internal.xsltc.dom.SimpleResultTreeImpl;

public class Solution79 {

    public static void main(String[] args) {
        char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        String word =  "ABCB";
        System.out.println(new Solution79().exist(board,word));
    }

    public boolean exist(char[][] board, String word) {
        int rowNum = board.length;
        int colNum = board[0].length;
        int[][] forbidden = new int[rowNum][colNum];
        for (int i = 0; i < rowNum; i++) {
            for (int j = 0; j < colNum; j++) {
                if(findWordInBoard(board, i, j, word, 0, forbidden)){
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean findWordInBoard(char[][] board, int starti, int startj, String word, int wordi, int[][] forbidden){
        /**
         * 用于递归查找的函数，starti, startj是当前开始对比的board格子下标，wordi是当前要对比的word字符下标，forbidden记录禁忌搜索
         */
        if (wordi == word.length()) return true; //word已被全部找到
        if(starti<0 || starti>board.length-1 || startj<0 || startj>board[0].length-1) return false;//搜索到board边界了
        if(forbidden[starti][startj]==1) return false; //当前格子已被搜索过
        if(board[starti][startj]!=word.charAt(wordi)) return false;//当前格子和要查找的word元素不同

        //word还没找齐，从当前格子向附近继续查找
        forbidden[starti][startj] = 1; //向附近查找前先把当前格子设为禁忌，防止回溯
        if (findWordInBoard(board, starti, startj - 1, word, wordi+1, forbidden)) {//向左把剩余的word找到了
            return true;
        }
        if (findWordInBoard(board, starti, startj + 1, word, wordi+1, forbidden)) {//向右把剩余的word找到了
            return true;
        }
        if (findWordInBoard(board, starti - 1, startj, word, wordi+1, forbidden)) {//向上把剩余的word找到了
            return true;
        }
        if (findWordInBoard(board, starti + 1, startj, word, wordi+1, forbidden)) {//向下把剩余的word找到了
            return true;
        }
        //上下左右都找不齐
        forbidden[starti][startj] = 0; //放开禁忌
        return false;
    }
}
